// [3362]零数组变换 III
struct Solution;

//leetcode submit region begin(Prohibit modification and deletion)
impl Solution {
    pub fn max_removal(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> i32 {
        let mut queries = queries;
        queries.sort_by(|a, b| a[0].cmp(&b[0]));
        let mut heap = std::collections::BinaryHeap::new();
        let mut delta_array = vec![0; nums.len() + 1];
        let mut operations = 0;
        let mut j = 0;

        for i in 0..nums.len() {
            operations += delta_array[i];
            while j < queries.len() && queries[j][0] == i as i32 {
                heap.push(queries[j][1]);
                j += 1;
            }
            while operations < nums[i] && !heap.is_empty() && *heap.peek().unwrap() >= i as i32 {
                operations += 1;
                let end = heap.pop().unwrap() as usize;
                delta_array[end + 1] -= 1;
            }
            if operations < nums[i] {
                return -1;
            }
        }
        heap.len() as i32
    }
}
//leetcode submit region end(Prohibit modification and deletion)


#[test]
fn main() {
    let nums = vec![2,0,2];
    let queries = vec![
        vec![0,2],
        vec![0,2],
        vec![1,1]
    ];
    assert_eq!(Solution::max_removal(nums, queries), 1);

    let nums = vec![1,1,1,1];
    let queries = vec![
        vec![1,3],
        vec![0,2],
        vec![1,3],
        vec![1,2]
    ];
    assert_eq!(Solution::max_removal(nums, queries), 2);

    let nums = vec![1,2,3,4];
    let queries = vec![
        vec![0,3]
    ];
    assert_eq!(Solution::max_removal(nums, queries), -1);
}